#include "BStree.h"

int Find(BSTreeNode *root,DataType data)
{
  BSTreeNode *cur = root;
  while(cur!=NULL)
  {
    if(cur->data == data)
    {
      return 1;
    }
    if(cur->data>data)
    {
      cur = cur->left;
    }
    else 
    {
      cur = cur->right;
    }
    
  }
  return 0;
}

BSTreeNode *BuyNode(DataType data)
{
    BSTreeNode *NewNode = (BSTreeNode *)malloc(sizeof(BSTreeNode));
    NewNode->data = data;
    NewNode->left = NewNode->right = NULL;
    return NewNode;
}


void BSTreeInsert(BSTreeNode **root,DataType data)
{
  BSTreeNode *cur = *root;
  BSTreeNode *parent = cur;
  while(cur !=NULL)
  {
    if(cur->data == data)
      return;
    parent = cur;
    if(cur->data > data)
    {
      cur = cur->left;
    }
    else 
    {
      cur = cur->right;
    }
  }
  if(parent == NULL)
  {
    *root = BuyNode(data);
    return;
  }
  if(parent->data > data)
  {
    parent->left = BuyNode(data);
    return;
  }
  if(parent->data < data)
  {
    parent->right = BuyNode(data);
  }

}

void PrintBStree(BSTreeNode *root)
{
  if(root !=NULL)
  {
    PrintBStree(root->left);
    printf("%d ",root->data);
    PrintBStree(root->right);
  }
}


void Delete(BSTreeNode **root,BSTreeNode *del_parent,BSTreeNode *del)
{
  if(del->left == NULL)
  {
    if(del_parent == NULL)
    {
      *root = del->right;
      free(del);
      return;
    }

    if(del_parent->right == NULL)
    {
      del_parent->left = del->right;
    }
    else{
      del_parent->right = del->right;
    }
    free(del);
    return;
  }
  else if(del->right == NULL)
  {
    if(del_parent == NULL)
    {
      *root = del->left;
      free(del);
      return;
    }

    if(del_parent->right == NULL)
    {
      del_parent->left = del->left;
    }
    else{
      del_parent->right = del->left;
    }
    free(del);
    return;
  }
  else 
  {
    //左右都不为空
    //替换删除
    //1. 找右子树最小值替换删除
    //2. 找左子树最大值替换删除
    BSTreeNode *cur = del->right;
    BSTreeNode *cur_parent = del;
    //采用第一种方法替换删除
    while(cur->left != NULL)
    {
      cur_parent = cur;
      cur = cur->left;
    }
    if(cur_parent == del)
    {
      del->data = cur->data;
      del->right = cur->right;
    }
    else 
    {
      del->data = cur->data;
      cur_parent->left = cur->right; 
    }
    free(cur);
  }


}

void RmoveBStreeNode(BSTreeNode **root,DataType data)
{
  BSTreeNode *del = *root;
  BSTreeNode *del_parent = NULL;
  while(del !=NULL)
  {
    if(del->data == data)
    {
      Delete(&*root,del_parent,del);
    }
    del_parent = del;
    if(del->data > data)
    {
      del = del->left;
    }
    else 
    {
      del = del->right;
    }
  }
}

